#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>

void Next(char* sup, int* next, int suplen)
{
	     next[0] = -1;
		 if (suplen > 1)
			 next[1] = 0;
		 else
			 return;

		 int i = 2;
		 int k = 0;
		 while (i < suplen)
		 {
			 if (k==-1||sup[k] == sup[i - 1])
			 {
				 next[i] = k + 1;
				 k++;
				 i++;
			 }
			 else
			 {
				 k = next[k];
			 }
		 }
}


int Kmp(char* str, char* sup)
{
	assert(str && sup);
	int len1 = strlen(str);
	int len2 = strlen(sup);

	int* next = (int*)malloc(sizeof(int) * len2);
	assert(next != NULL);
	Next(sup, next, len2);

	int i = 0;
	int j = 0;
	while (i < len1 && j < len2)
	{
		if (j == -1 || str[i] == sup[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}

	if (i >= len1 && j < len2)
	{
		return -1;
	}
	else
	{
		return i - j;
	}

	free(next);
	next = NULL;
}

int main()
{
	char str[] = "abcdabcdeabc";
	char sup[] = "abc";
	char sup1[] = "abcde";
	char sup2[] = "dkd";
	printf("%d\n%d\n%d\n", Kmp(str, sup), Kmp(str, sup1), Kmp(str, sup2));


	return 0;
}